package leetcode.jianzhioffer;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-28 17:22
 **/
public class JianZhiOffer26 {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //首先A节点或B节点为空，直接返回false
        //然后判断以A节点为根节点的子树是否包含树B
        //如果不满足上一个条件，就判断判断以A.left节点为根节点的子树是否包含树B
        //如果不满足上一个条件，就判断判断以A.right节点为根节点的子树是否包含树B
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }

    private boolean recur(TreeNode A, TreeNode B) {
        //如果B为空，说明遍历结束，B为A的子结构
        if (B == null) {
            return true;
        }
        //如果A为空，说明已经越过A叶子结点，匹配失败
        if (A == null || B.val != A.val) {
            return false;
        }
        //继续判断B的左右节点是否与A的左右节点相同
        return recur(A.left, B.left) && recur(A.right, B.right);
    }

    public static void main(String[] args) {
        JianZhiOffer26 offer = new JianZhiOffer26();
        TreeNode node = new TreeNode(1);
        TreeNode temp = node;
        temp.left = new TreeNode(2);
        temp.right = new TreeNode(3);
        TreeNode B = temp.right;
        temp = temp.left;
        temp.left = new TreeNode(4);
        System.out.println("offer.isSubStructure(node ,B) = " + offer.isSubStructure(node, B));
    }

}
